package Text1;

import java.util.*;

public class Main {
    public static final int N=20;
    public static int n;
    public static int[] st=new int[N];// 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
//    从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n=scanner.nextInt();
        dfs(1);
    }

    public static void dfs(int u) {
        if(u>n){
            for (int i = 1; i <= n ; i++) {
                if(st[i]==1){
                    System.out.print(i+" ");
                }
            }
            System.out.println();
            return;
        }
        // 第一个分支：不选
        st[u]=2;
        dfs(u+1);
        st[u]=0;
        // 第二个分支：选
        st[u]=1;
        dfs(u+1);
        st[u]=0;
    }
}
